{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2 机智的外卖员\n",
    "### 2.1 题目\n",
    "题目2：机制的外卖员\n",
    "<br/>外卖员每天在大厦中送外卖，大厦共有L层（0<L<=10^5），当他处于第N层楼时，可以每分钟通过步行梯向上达到N+1层，或向下达到N-1层，\n",
    "<br/>或者乘坐电梯达到2*N层。给定他所处位置N，以及外卖配送的目的楼层M，计算他送达的最短时间\n",
    "<br/>1\n",
    "<br/>2\n",
    "<br/>输入：5 17\n",
    "<br/>输出：4\n",
    "\n",
    "### 2.2 解析\n",
    "直觉是动态规划, 子问题拆解碰到问题:\n",
    "<br/> 从第N层到第i层, 方式只可能有三条:\n",
    "<br/> 1)先到第i-1层, 再上一层, 即d[i-1]+1\n",
    "<br/> 2)先到i+1层, 再下一层, 即d[i+1]+1\n",
    "<br/> 3)如果i是偶数, 还可能是从i/2层坐电梯上来, 即d[i/2]+1\n",
    "<br/> 但这样d[i]依赖d[i+1]无法使用动态规划(d为最短路径函数)\n",
    "<br/> \n",
    "<br/> 下面证明方式2中到i+1层的方式一定是坐电梯直接到的, 否则一定不是最短路径:\n",
    "<br/> 要到i+1层同样只有两种方式:\n",
    "<br/> 1)从第i层上来, 不可能\n",
    "<br/> 快递员要到i层, 因此不可能是从i层走上来的, 除非傻了\n",
    "<br/> 2)从坐电梯到第i+1+k层走下来, k >= 0, k=0时不用走\n",
    "<br/> 2.1)如果i为偶数, k定为奇数, 总路程s1为: d[(i+1+k)/2]+1+(k+1)\n",
    "<br/> 而另一方面, 到第i/2层的最短路径一定小于等于先到d[i/2+(k+1)/2]再下楼到i/2层, 因为这是其中的一条路径\n",
    "<br/> 即, d[i/2] <= d[i/2+(k+1)/2] + (k+1)/2\n",
    "<br/> 因此先到i/2层再坐电梯到i层的路程s2有:\n",
    "<br/> s2 = d[i/2]+1 <= d[i/2+(k+1)/2]+1+(k+1)/2 <d[(i+1+k)/2]+1+(k+1) = s1\n",
    "<br/> 所以此时s1一定不是最短路径\n",
    "<br/> 2.2)如果i为奇数, k一定为偶数, 总路程s1为: d[(i+1+k)/2]+1+(k+1)\n",
    "<br/> 到(i+1)/2层的最短路径一定小于等于其中的一条: 到(i+1)/2+k/2层然后再走下楼\n",
    "<br/> 即: d[(i+1)/2] <= d[(i+1)/2+k/2]+k/2\n",
    "<br/> 因此因此先到(i+1)/2层再坐电梯到i+1层再到第i层的路程s2有:\n",
    "<br/> s2 = d[(i+1)/2] + 1 + 1 <= d[(i+1)/2+k/2]+k/2+1+1 <= d[(i+1+k)/2]+1+(k+1)=s1\n",
    "<br/> 当且仅当k=0时等号成立\n",
    "<br/> 2.3)综上, 最短路径中, 到i+1层然后下楼到i层只有一种情况, 即先坐电梯到i+1层然后走下来\n",
    "<br/> \n",
    "<br/> 因此子问题可以拆解为:\n",
    "<br/> 从第N层到第i层, 方式只可能有三条:\n",
    "<br/> 1)先到第i-1层, 再上一层, 即d[i-1]+1\n",
    "<br/> 2)如果i为奇数, 可能坐电梯到i+1层下楼到第i层, 即d[(i+1)/2]+1+1\n",
    "<br/> 3)如果i是偶数, 还可能是从i/2层坐电梯上来, 即d[i/2]+1\n",
    "<br/> \n",
    "<br/> 此时d[i]只依赖小于i的函数值, 可以使用动态规划"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4 5->4->8->16->17\n",
      "3 3->4->5->10\n"
     ]
    }
   ],
   "source": [
    "def get_path(transit: dict, n: int, m: int):\n",
    "    \"\"\"\n",
    "    获取路径\n",
    "    :param transit: 中转节点 如果从n到i需要经过j则有transit[i]=j\n",
    "    :param n: 外卖员的起始楼层\n",
    "    :param m: 外卖员的目标楼层\n",
    "    :return: 路程\n",
    "    \"\"\"\n",
    "    s = m\n",
    "    path = []\n",
    "    while s != n:\n",
    "        path.insert(0, s)\n",
    "        if s in transit:\n",
    "            s = transit[s]\n",
    "        else:\n",
    "            s = n\n",
    "    path.insert(0, n)\n",
    "    return path\n",
    "\n",
    "\n",
    "def road_plan(n: int, m: int):\n",
    "    \"\"\"\n",
    "    路径规划\n",
    "    :param n: 外卖员的起始楼层\n",
    "    :param m: 外卖员的目标楼层\n",
    "    :return: 路程消耗的时间(分钟), 路径\n",
    "    \"\"\"\n",
    "    if n >= m:\n",
    "        return n - m\n",
    "    transit = {}\n",
    "    # 第1,2,3,...,m, 为了索引方便前面加一个第0层\n",
    "    d = [abs(n - i) for i in range(0, m + 1)]\n",
    "    for i in range(n + 1, m + 1):\n",
    "        s1 = d[i - 1] + 1\n",
    "        if i % 2:\n",
    "            s2 = d[(i + 1) // 2] + 1 + 1\n",
    "        else:\n",
    "            s2 = d[i // 2] + 1\n",
    "\n",
    "        if s1 <= s2:\n",
    "            transit[i] = i - 1\n",
    "            d[i] = s1\n",
    "        else:\n",
    "            d[i] = s2\n",
    "            transit[i] = (i + 1) // 2 if i % 2 else i // 2\n",
    "    return d[m], get_path(transit, n, m)\n",
    "\n",
    "\n",
    "dst1, path1 = road_plan(5, 17)\n",
    "print(dst1, '->'.join([str(each) for each in path1]))\n",
    "dst2, path2 = road_plan(3, 10)\n",
    "print(dst2, '->'.join([str(each) for each in path2]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
